#include"Tree.h"

void Create(BiTree &T)
{
	char ch;
	cin >> ch;
	if (ch == '#') T = NULL;
	else
	{
		T = new BTNode;
		T->data = ch;
		Create(T->lchild);
		Create(T->rchild);
	}
}

void PreOrderTraverse(BiTree T)
{
	if (!T)
		return;
	cout << T->data;
	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rchild);
}

void InOrderTraverse(BiTree T)
{
	if (!T)
		return;
	InOrderTraverse(T->lchild);
	cout << T->data;
	InOrderTraverse(T->rchild);
}

void PostOrderTraverse(BiTree T)
{
	if (!T)
		return;
	PostOrderTraverse(T->lchild);
	PostOrderTraverse(T->rchild);
	cout << T->data;
}

void iter_PreOrderTraverse(BiTree T)
{
	if (!T)
		return;
	BTNode* PMove = T;
	stack<BTNode*> stk;
	while (PMove || !stk.empty())
	{
		while (PMove)
		{
			stk.push(PMove);
			cout << PMove->data;
			PMove = PMove->lchild;
		}
		if(!stk.empty())
		{
			PMove=stk.top();
			stk.pop();
			PMove = PMove->rchild;
			
		}
	}
}

void iter_InOrderTraverse(BiTree T)
{
	if (!T)
		return;
	BTNode* PMove = T;
	stack<BTNode*> stk;
	while (PMove || !stk.empty())
	{
		while (PMove)
		{
			stk.push(PMove);
			PMove = PMove->lchild;
		}
		if (!stk.empty())
		{
			PMove = stk.top();
			stk.pop();
			cout << PMove->data;
			PMove = PMove->rchild;
		}
	}
}


void LevelOrderTraverse(BiTree T)
{
	queue<BTNode*> level;
	level.push(T);
	while (!level.empty())
	{
		for (int i = 0; i < level.size(); ++i)
		{
			T=level.front();
			cout << T->data;
			level.pop();
			if (T->lchild) level.push(T->lchild);
			if (T->rchild) level.push(T->rchild);
		}
	}

}